//题目:
// 给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词word的重复值为 k。
// 单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。
// 如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
// 给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

// 示例 1：
// 输入：sequence = "ababc", word = "ab"
// 输出：2
// 解释："abab" 是 "ababc" 的子字符串。

// 示例 2：
// 输入：sequence = "ababc", word = "ba"
// 输出：1
// 解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

// 示例 3：
// 输入：sequence = "ababc", word = "ac"
// 输出：0
// 解释："ac" 不是 "ababc" 的子字符串。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int maxRepeating(string sequence, string word) 
    {
        //题意：求sqquence中word最长连续重复子串的个数
        // int n=sequence.size(),m=word.size();
        // //1.创建dp表————dp[i][j]表示：在sequence的[i,j]子串中，word最长连续重复子串的个数
        // vector<vector<int>> dp(n+1,vector<int>(n+1));
        // //2.初始化
        // //3.填表————动态转移方程：dp[i]=dp[i-1];for(int j=word.size()-1;j>=0;j--)if(word[j]!=sq[])
        // int ret=0;
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=i;j<=n;j++)
        //     {
        //         dp[i][j]=dp[i][j-1];
        //         for(int k=m-1;k>=0;k--)
        //         {
        //             //连续重复子串长度
        //             if(j+k-m<i-1 || word[k]!=sequence[j+k-m] || dp[i][j]!=dp[i][j+k-m+1])
        //                 break;
        //             //*连续*  前面不存在 || 若前面存在：sequence[j-m]不能被前面使用(dp[i][j]==dp[i][j-m]) && sequence[j-m-1]被前面使用(dp[i][j]!=dp[i][j-m-1])
        //             if(k==0 && (dp[i][j-m+1]==0 || (dp[i][j]==dp[i][j-m] && dp[i][j]!=dp[i][j-m-1]))) dp[i][j]+=1;
        //         }
        //         ret=max(ret,dp[i][j]);
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // //4.确定返回值
        // return ret;

        //空间优化
        int n=sequence.size(),m=word.size();
        //1.创建dp表————dp[i][j]表示：在sequence的[i,j]子串中，word最长连续重复子串的个数
        vector<int> dp(n+1);
        //2.初始化
        //3.填表————动态转移方程：dp[i]=dp[i-1];for(int j=word.size()-1;j>=0;j--)if(word[j]!=sq[])
        int ret=0;
        for(int i=1;i<=n;i++)
        {
            std::fill(dp.begin(), dp.end(), 0);
            for(int j=i;j<=n;j++)
            {
                dp[j]=dp[j-1];
                for(int k=m-1;k>=0;k--)
                {
                    //子串匹配
                    if(j+k-m<i-1 || word[k]!=sequence[j+k-m] || dp[j]!=dp[j+k-m+1])
                        break;
                    //*连续*  前面不存在 || 若前面存在：sequence[j-m]不能被前面使用(dp[i][j]==dp[i][j-m]) && sequence[j-m-1]被前面使用(dp[i][j]!=dp[i][j-m-1])
                    if(k==0 && (dp[j-m+1]==0 || (dp[j]==dp[j-m] && dp[j]!=dp[j-m-1]))) dp[j]+=1;
                }
                ret=max(ret,dp[j]);
                cout<<dp[j]<<" ";
            }
            cout<<endl;
        }
        //4.确定返回值
        return ret;
    }
};